import java.util.HashMap;
import java.util.Map;

//和可被 K 整除的子数组
//测试链接 https://leetcode.cn/problems/subarray-sums-divisible-by-k/description/
public class SubarraysDivByK {
    public int subarraysDivByK(int[] nums, int k) {
        Map<Integer,Integer> map = new HashMap<>();
        map.put(0,1);
        int ret = 0, sum = 0;
        for(int num : nums){
            sum += num;  //计算前缀和

            int in = ( sum % k + k ) % k;
            ret += map.getOrDefault(in,0);
            map.put(in, map.getOrDefault(in,0) + 1);
        }

        return ret;
    }
}
